#!/usr/bin/env python
# coding: utf-8

# In[1]:


"""普通方法遍历整个矩阵"""

class Solution:
    def Matrix(self, matrix, target): 
        # 定义矩阵函数搜索目标值，逐个对比遍历，找出目标值
        for num in matrix:
            if target in num:
                return True
        return False

# 输入示例矩阵和目标值进行试验
matrix = eval(input("请输入矩阵:\n"))
# 输入 matrix = [[1, 4, 7, 11, 15],[2, 5, 8, 12, 19],[3, 6, 9, 16, 22],[10, 13, 14, 17, 24],[18, 21, 23, 26, 30]]
n = int(input("请输入目标值:\n"))
# 输入 5 或 20
solution = Solution()
print(solution.Matrix(matrix, n)) 


# In[ ]:


"""二分法搜索目标值"""

class Solution:
    def Matrix1(self, matrix, target):
        n = len(matrix[0])     # 取矩阵列的长度
        for i in range (0,n):
            m = len(matrix)    # 取矩阵行的长度
            left = 0           # 将矩阵行中第一个元素作为遍历左方第一个
            right = m - 1      # 将矩阵行中最后一个元素作为遍历右方第一个
            
            while left <= right:
                mid = (left + right) // 2
                # 取左右边界内中心元素作为中间数的索引值
                if matrix[mid][i] == target:
                    return True
                elif matrix[mid][i] > target:
                    right = mid-1
                else:
                        left = mid+1
        return False
        # 行为升序排列，因此对行进行二分查找，每行遍历
        # 不断调整左右边界和中间数的索引值，直到中间值为目标值返回True，否则为False
 
# 输入示例矩阵和目标值进行试验
matrix = eval(input("请输入矩阵:\n"))
# 输入 matrix = [[1, 4, 7, 11, 15],[2, 5, 8, 12, 19],[3, 6, 9, 16, 22],[10, 13, 14, 17, 24],[18, 21, 23, 26, 30]]
t = int(input("请输入目标值:\n"))
solution = Solution()
print(solution.Matrix1(matrix, t)) 


# In[ ]:




